package org.cllib.geometry;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Stack;

public class GeometryUtil {
	public static class Point{
		public int x , y;

		public Point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
		
		
	}
	
	public static class Line{
		public int x1 , y1 , x2 , y2;
		
		public Line(Line anotherLine){
			this.x1 = anotherLine.x1;
			this.y1 = anotherLine.y1;
			this.x2 = anotherLine.x2;
			this.y2 = anotherLine.y2;
		}
	}
	public final static boolean debug = false;
	
	public static void debug(String s){
		if(debug){
			System.out.println(s);
		}
	}
	
	public static int fx(int x1 , int y1 , int x2 , int y2 , int x){
		if(x1 == x2 && y1 == y2){
			throw new IllegalArgumentException("unable to compute fx for point[" + x1 + " , " + y1 + "]");
		}
		
		if(x1 == x2){
			throw new IllegalArgumentException("unalbe to compute fx for vertical line");
		}
		
		return (x * (y2 - y1) + x2 * y1 - x1 * y2) / (x2 - x1);
	}
	
//	public static Point getIntersection(Line l1 , Line l2){
////		if(k == 0){
////			throw new IllegalArgumentException("unable to get intersection for paralell lines " + l1 + " and " + l2);
////		}
//		
//		final int fxy1 = fxy(l1 , l2.x1 , l2.y1);
//		final int fxy2 = fxy(l1 , l2.x2 , l2.y2);
//		
//		if(fxy1 == 0 && fxy2 == 0){
//			throw new IllegalArgumentException("unable to get intersectioni for superposition lines " + l1 + " and " + l2);
//		}
//		
//		if((fxy1 & 0x80000000) == (fxy2 & 0x80000000)){
//			throw new IllegalArgumentException("unable to get intersection for " + l1 + " and " + l2 + " no intersection");
//		}
//		
//		//deal with points here
//		if(l1.x2 == l1.x1 && l1.y2 == l1.y1){
//			return new Point(l1.x1 , l1.y1);
//		}
//		
//		if(l2.x2 == l2.x1 && l2.y2 == l2.y1){
//			return new Point(l2.x1 , l2.y1);
//		}
//		
//		final int k = (l1.y2 - l1.y1) * (l2.x2 - l2.x1) - (l2.y2 - l2.y1) * (l1.x2 - l1.x1);
//		
//		final int dx1 = l1.x2 - l1.x1;
//		final int dy1 = l1.y2 - l1.y1;
//		
//		final int dx2 = l2.x2 - l2.x1;
//		final int dy2 = l2.y2 - l2.y1;
//		
//		final int m1 = l1.x2 * l1.y1 - l1.x1 * l1.y2;
//		final int m2 = l2.x2 * l2.y1 - l2.x1 * l2.y2;
//		
//		if(l1.x1 == l1.x2){
//			if(l2.y1 == l2.y2){
//				return new Point(l1.x1 , l2.y1); 
//			}
//			
//			return new Point(l1.x1 , (l1.x1 * (dy2) + m2) / (dx2));
//		}
//		
////		int ix = ((l1.x2 - l1.x1) * (l2.x2 * l2.y1 - l2.x1 * l2.y2) - (l2.x2 - l2.x1) * (l1.x2 * l1.y1 - l1.x1 * l1.y2)) / ((l1.y2 - l1.y1) * (l2.x2 - l2.x1) - (l2.y2 - l2.y1) * (l1.x2 - l1.x1)) ;
////		int iy = (ix * (l1.y2 - l1.y1) + l1.x2 * l1.y1 - l1.x1 * l1.y2) / (l1.x2 - l1.x1);
//		
//		final int ix = ((dx1) * (m2) - (dx2) * (m1)) / k;
//		final int iy = (ix * (dy1) + m1) / (dx1);
//		
//		return new Point(ix , iy);
//	}
	
	//FIXME need to work on the precision of this method
	public static Point[] getIntersection2(Line l1 , Line l2){
		final int fxyl11 = fxy(l1 , l2.x1 , l2.y1);
		final int fxyl12 = fxy(l1 , l2.x2 , l2.y2);
		
		final int fxyl21 = fxy(l2 , l1.x1 , l1.y1);
		final int fxyl22 = fxy(l2 , l1.x2 , l1.y2);
		
		if((fxyl11 == 0 && fxyl12 == 0) || (fxyl21 == 0 && fxyl22 == 0)){
			throw new UnsupportedOperationException("unable to get intersection for superposition lines " + l1 + " and " + l2);
//			throw new IllegalArgumentException("unable to get intersection for superposition lines " + l1 + " and " + l2);
//			return new Point[]{};
		}
		
		if(fxyl11 != 0 && fxyl12 != 0 && fxyl21 != 0 && fxyl22 != 0){
			if((fxyl11 & 0x80000000) == ((fxyl12 & 0x80000000)) || (fxyl21 & 0x80000000) == (fxyl22 & 0x80000000)){
				return new Point[0];
			}
		}
		
		//deal with points here
		if(l1.x2 == l1.x1 && l1.y2 == l1.y1){
			return new Point[]{new Point(l1.x1 , l1.y1)};
		}
		
		if(l2.x2 == l2.x1 && l2.y2 == l2.y1){
			return new Point[]{new Point(l2.x1 , l2.y1)};
		}
		
		if(l1.x1 == l1.x2){
			int x = l1.x1;
			int y = fx(l2,l1.x1);
			
			return new Point[]{new Point(x , y)};
		}
		
		if(l2.x1 == l2.x2){
			int x = l2.x1;
			int y = fx(l1,l2.x1);
			
			return new Point[]{new Point(x , y)};
		}
		
		final long k = (l1.y2 * 1L - l1.y1 * 1L) * (l2.x2 * 1L - l2.x1 * 1L) - (l2.y2 * 1L - l2.y1 * 1L) * (l1.x2 * 1L - l1.x1 * 1L);
		
		final long dx1 = l1.x2 * 1L - l1.x1 * 1L;
		final long dy1 = l1.y2 * 1L - l1.y1 * 1L;
		
		final long dx2 = l2.x2 * 1L - l2.x1 * 1L;
		final long dy2 = l2.y2 * 1L - l2.y1 * 1L;
		
		final long m1 = l1.x2 * 1L * l1.y1 * 1L - l1.x1 * 1L * l1.y2 * 1L;
		final long m2 = l2.x2 * 1L * l2.y1 - l2.x1 * 1L * l2.y2;
		
//		if(l1.x1 == l1.x2){
//			if(l2.y1 == l2.y2){
//				return new Point[]{new Point(l1.x1 , l2.y1)}; 
//			}
//			
//			return new Point[]{new Point(l1.x1 , (l1.x1 * (dy2) + m2) / (dx2))};
//		}
		
//		int ix = ((l1.x2 - l1.x1) * (l2.x2 * l2.y1 - l2.x1 * l2.y2) - (l2.x2 - l2.x1) * (l1.x2 * l1.y1 - l1.x1 * l1.y2)) / ((l1.y2 - l1.y1) * (l2.x2 - l2.x1) - (l2.y2 - l2.y1) * (l1.x2 - l1.x1)) ;
//		int iy = (ix * (l1.y2 - l1.y1) + l1.x2 * l1.y1 - l1.x1 * l1.y2) / (l1.x2 - l1.x1);
		
//		final int ix = ((dx1) * (m2) - (dx2) * (m1)) / k;
//		final int iy = (ix * (dy1) + m1) / (dx1);
		
//		final double ix = ((dx1) * (m2) - (dx2) * (m1)) * 1.0 / k;
//		final double iy = (ix * (dy1) + m1) * 1.0 / (dx1);
		
		final int scale = 10000;
		
		final long ix = ((dx1 * 1L) * (m2) - (dx2 * 1L) * (m1)) * scale / k;
		final long iy = (ix * (dy1) + m1 * scale) / (dx1);
		
//		if(ix < 0 || iy < 0){
//			System.out.println("************************************************");
//			System.out.println(ix);
//			System.out.println(dy1);
//			System.out.println(m1);
//			System.out.println((ix * (dy1) + m1 * scale));
//			System.out.println(dx1);
//		}
//		final int a1 = ((dx1) * (m2) - (dx2) * (m1));
//		final int b1 = k;
//		
//		final int a2 = (ix * (dy1) + m1);
//		final int b2 = dx1;
		
//		System.out.println("a1= "+ a1 +" b1= " + b1 + " a2= " + a2 + " b2=" + b2);
		
		final Point p = new Point((int)ix / scale, (int)iy / scale);
		
//		System.out.println(p.x + " " + p.y);
		
		return new Point[]{p};
	}
	
	public static int fx(Line line , int x){
		return fx(line.x1 , line.y1 , line.x2 , line.y2 , x);
	}
	
	public static int fy(int x1 , int y1 , int x2 , int y2 , int y){
		if(x1 == x2 && y1 == y2){
			throw new IllegalArgumentException("unable to compute fy for point[" + x1 + " , " + y1 + "]");
		}
		
		if(y1 == y2){
			throw new IllegalArgumentException("unalbe to compute fy for horizontal line");	
		}
		
		return (y * (x2 - x1) + x1 * y2 - x2 * y1) / (y2 - y1);
	}
	
	public static int fxy(int x1 , int y1 , int x2 , int y2 , int x , int y){
		return y * (x2 - x1) + x * (y1 - y2) + x1 * y2 - x2 * y1;
	}
	
	public static int fxy(Line l , Point p){
		return fxy(l.x1 , l.y1, l.x2 , l.y2 , p.x , p.y);
	}
	
	public static int fxy(Line l , int x ,int y){
		return fxy(l.x1 , l.y1, l.x2 , l.y2 , x , y);
	}
	
	public static Polygon generateConvexHull(int[] points){
		if(points.length < 6){
			throw new IllegalArgumentException("unable to generate convex hull for points less than 3");
		}
		
		if(points.length % 2 != 0){
			throw new IllegalArgumentException("number of coordinates should be even passed[" + points.length + "]");
		}
		
		Stack<Point> s = new Stack<Point>();
		
		int maxY = Integer.MIN_VALUE;
		int mi = -1;
		for (int i = 0; i < points.length - 1; i += 2) {
			int y = points[i + 1];
			
			if(y > maxY){
				maxY = y;
				mi = i;
			}
		}
		
		//make (points[0] , points[1]) the 1st point
		int temp = points[0];
		points[0] = points[mi];
		points[mi] = temp;
		
		temp = points[1];
		points[1] = points[mi + 1];
		points[mi + 1] = temp;
		
		//order the left points with respect of polar degrees against 1st point
		for (int i = 2; i < points.length - 2; i += 2) {
			for (int j = i + 2; j < points.length - 1; j += 2) {
				int nxi = points[i] - points[0];
				int nyi = points[1] - points[i + 1];
				
				int nxj = points[j] - points[0];
				int nyj = points[1] - points[j + 1];
				
				int xp = nxi * nyj - nxj * nyi;
				
				if(xp < 0 || (xp == 0 && points[i] < points[j])){
					temp = points[i];
					points[i] = points[j];
					points[j] = temp;
					
					temp = points[i + 1];
					points[i + 1] = points[j + 1];
					points[j + 1] = temp;					
				}
			}
		}
		
		s.push(new Point(points[0] , points[1]));
		s.push(new Point(points[2] , points[3]));
		s.push(new Point(points[4] , points[5]));
		
		//for each point in the collection
		for (int i = 6; i < points.length - 1; i+= 2) {
			Point cp = new Point(points[i] , points[i + 1]);
			
			int f = -1;
			
			do{
				Point tp = s.pop();
				Point tp2 = s.pop();
				
				s.push(tp2);
				s.push(tp);
				
				int x1 = tp.x - tp2.x;
				int y1 = tp2.y - tp.y;
				
				int x2 = cp.x - tp2.x;
				int y2 = tp2.y - cp.y;
				
				f = x1 * y2 - x2 * y1;
				
				if(f <= 0){
					Point p = s.pop();
				}
			}while(f <= 0);
			
			s.push(cp);
		}
		
		int[] result = new int[s.size() * 2];
		int index = result.length - 1;
		
		while(!s.isEmpty()){
			Point p = s.pop();
			
			result[index --] = p.y;
			result[index --] = p.x;
		}
		
		return new Polygon(result);
	}
	
	public static class LineGroup{
		final Line l1 , l2;
		public final int x,  y;
		
		public LineGroup(Line l1 , Line l2 , int x, int y){
			this.l1 = l1;
			this.l2 = l2;
			this.x = x;
			this.y = y;
		}
		
		public LineGroup(Line l1 , Line l2 , Point p){
			this(l1, l2, p.x, p.y);
			
		}
	}
	
	public static LineGroup[] getIntersectionPoints4Lines(Line[] lines){
		debug("*****************************START SWEEP LINE*****************************");
		debug("SWEEP LINE INPUT " + Arrays.toString(lines));
		
		if (lines.length == 0) {
			return new LineGroup[0];
		}
		
		final Line[] backup = lines;
		
		lines = new Line[lines.length];
		for (int i = 0; i < backup.length; i++) {
			lines[i] = new Line(backup[i]);
		}
		
		final List<LineGroup> lgs = new ArrayList<LineGroup>();
		
		class PointItem {
			public final static int START_POINT = 0;
			public final static int END_POINT = 1;
			
			final int x, y;
			final Line line;
			final int type;
			public PointItem(int x, int y, Line line , int type) {
				super();
				this.x = x;
				this.y = y;
				this.line = line;
				this.type = type;
			}
		}
		
		//sort the start points according to x
		for (int i = 0; i < lines.length ; i++) {
			Line line = lines[i];
			
//			if(line.x1 == line.x2 && line.y1 == line.y2){
//				throw new IllegalArgumentException("point found [" + line.x1 + " , " + line.y1 + "]");
//			}
			
			if(line.x1 > line.x2){
				int temp = line.x1;
				line.x1 = line.x2;
				line.x2 = temp;
				
				temp = line.y1;
				line.y1 = line.y2;
				line.y2 = temp;
			}
		}
		
		List<PointItem> pis = new ArrayList<PointItem>();
		
		//when a start point of a line is encountered , put the line into consideration
		//sort the lines according to their start points' y values
		for (int i = 0; i < lines.length; i++) {
			Line l = lines[i];
			
			PointItem pi = new PointItem(l.x1 , l.y1 , l , PointItem.START_POINT);
			pis.add(pi);
			
			pi = new PointItem(l.x2 , l.y2 , l , PointItem.END_POINT);
			pis.add(pi);
		}
		
		for (int i = 0; i < pis.size() - 1; i++) {
			for (int j = i + 1; j < pis.size(); j++) {
				PointItem pi = pis.get(i);
				PointItem pj = pis.get(j);
				
				if(pi.x > pj.x){
					pis.set(i, pj);
					pis.set(j, pi);
				}
			}
		}
		
		final List<Line> l = new ArrayList<Line>();
		
		for (int i = 0; i < pis.size(); i++) {
			final PointItem pi = pis.get(i);
			
			if(pi.type == PointItem.START_POINT){
				//just put it in the line list with respect of y at x
				Line line = pi.line;
				
				l.add(line);
				
				Collections.sort(l, new Comparator<Line>(){

					public int compare(Line o1, Line o2) {
						// TODO Auto-generated method stub
						final int x = pi.x;
						
						int y1 = 0;
						int y2 = 0;
						
						if(o1.x1 == o1.x2 && o2.x1 == o2.x2){
							return Math.min(o1.y1 , o1.y2) - Math.min(o2.y1 , o2.y2);
						}else if(o1.x1 == o1.x2){
							y2 = fx(o2 , x);
							return Math.min(o1.y1, o1.y2) - y2;
						}else if(o2.x1 == o2.x2){
							y1 = fx(o1 , x);
							return y1 - Math.min(o2.y1, o2.y2);
						}
						
						y1 = fx(o1 , x);
						y2 = fx(o2 , x);
						
						if(y1 == y2){
							//same start point
							debug("START POINT INTERSECTION " + o1 + " AND " + o2 + " POINT [" + x + " , " + y1 + "]");
							lgs.add(new LineGroup(o1, o2 , x , y1));
						}
						
						return y1 - y2;
					}
					
				});
			}else{
				//check intersection if find put into line group
				final Line l1 = pi.line;
				
				final int x = pi.x;
				
				for (int j = 0; j < l.size(); j++) {
					final Line l2 = l.get(j);
					
					if(l2 != l1){
						Point[] ps = getIntersection2(l1, l2);
						for (int k = 0; k < ps.length; k++) {
							lgs.add(new LineGroup(l1, l2 , ps[k]));
						}
//						int sx = Math.max(l1.x1, l2.x1);
//						
//						final int fxs1 = fx(l2, sx);
//						final int fxs2 = fx(l1 , sx);
//						
//						final int fxe1 = fx(l2, x);
//						final int fxe2 = fx(l1 , x);
//						
//						final int f = (fxs2 - fxs1) * (fxe2 - fxe1);
//						
//						//now judge whether two lines have intersection points 
//						
//						if(f > 0){
//							//no intersection just move on
//							debug("NO INTERSECTION " + l2 + " AND " + l1);
//						}else if(f == 0){
//							//start point already dealt , just check the end point
//							if(fxe1 == fxe2){
//								debug("SAME END POINT " + l2 + " AND " + l1 + " POINT [" + l2.x2 + " , " + l1.y2 + "]");
//								lgs.add(new LineGroup(l2, l1, x , fxe1));
//							}
//						}else {
//							//trick part intersection of 2 segment
////							final Line l1 = line;
////							final Line l2 = lj;
//							
////							int ix = ((l1.x2 - l1.x1) * (l2.x2 * l2.y1 - l2.x1 * l2.y2) - (l2.x2 - l2.x1) * (l1.x2 * l1.y1 - l1.x1 * l1.y2)) / ((l1.y2 - l1.y1) * (l2.x2 - l2.x1) - (l2.y2 - l2.y1) * (l1.x2 - l1.x1)) ;
////							int iy = (ix * (l1.y2 - l1.y1) + l1.x2 * l1.y1 - l1.x1 * l1.y2) / (l1.x2 - l1.x1);
//							
//							org.cllib.data.Point p = getIntersection(l1, l2);
//							
//							int ix = p.x;
//							int iy = p.y;
//							
//							debug("INTERSECTION " + l1 + " AND " + l2 + " POINT [" + ix + " , " + iy + "]");
//							
//							lgs.add(new LineGroup(l1, l2, ix , iy));
////							System.out.println("SIZE [" + lgs.size() + "]");
//						}
					}
				}
				
				l.remove(l1);
			}
		}
		
		//when reaching an end point find out the relationship of the lines
		//under control if their relative - relationship has changed they have intersection point
		//record it
		
		debug("*****************************END SWEEP LINE*****************************");
		//when all points are processed , done
		return lgs.toArray(new LineGroup[lgs.size()]);
	}
	
}
